package test_20220926;

//orderedArray.java
//demonstrates ordered array class
//to run this program: C>java OrderedApp
////////////////////////////////////////////////////////////////
public class OrdArray
{
private long[] a;                 // ref to array a
private int nElems;               // number of data items
//-----------------------------------------------------------
public OrdArray(int max)          // constructor
{
   a = new long[max];             // create array
   nElems = 0;
 }
//-----------------------------------------------------------
public int size()
   { return nElems; }
//-----------------------------------------------------------
public int find(long searchKey)
{
   int lowerBound = 0;
   int upperBound = nElems-1;
//     int curIn;

   while(true)
   {
      int curIn = (lowerBound + upperBound ) / 2;
      if(a[curIn]==searchKey)
         return curIn;              // found it
      else if(lowerBound > upperBound)
         return nElems;             // can't find it
      else                          // divide range
      {
         if(a[curIn] < searchKey)
            lowerBound = curIn + 1; // it's in upper half
         else
            upperBound = curIn - 1; // it's in lower half
      }  // end else divide range
   }  // end while
 }  // end find()
//-----------------------------------------------------------
public void insert(long value)    // put element into array
{
	  int i = 0;
	  int j = nElems-1;
	  if(j >= 0 && a[j] <= value) {
		  a[nElems++] = value;
		  return;
	  }
	  while(i < j) {
		  int mid = (i + j) / 2;
		  if(a[mid] >= value) {
			  j = mid;
		  }else {
			  i = mid + 1;
		  }
	  }
	  for(int k = nElems - 1; k >= i; k--) {
		  a[k + 1] = a[k];
	  }
	  a[i] = value;
	  nElems++;
	   
	   /*
   int j;
   for(j=0; j<nElems; j++)        // find where it goes
      if(a[j] > value)            // (linear search)
         break;
   for(int k=nElems; k>j; k--)    // move bigger ones up
      a[k] = a[k-1];
   a[j] = value;                  // insert it
   nElems++;                      // increment size
   */
 }  // end insert()
//-----------------------------------------------------------
public boolean delete(long value)
   {
   int j = find(value);
   if(j==nElems)                  // can't find it
      return false;
   else                           // found it
      {
      for(int k=j; k<nElems; k++) // move bigger ones down
         a[k] = a[k+1];
      nElems--;                   // decrement size
      return true;
      }
   }  // end delete()
//-----------------------------------------------------------
public void display()             // displays array contents
   {
   for(int j=0; j<nElems; j++)       // for each element,
      System.out.print(a[j] + " ");  // display it
   System.out.println("");
   }
//-----------------------------------------------------------
public static long[] merge(OrdArray arr, OrdArray brr) {
	   int size1 = arr.size();
	   int size2 = brr.size();
	   long[] res = new long[size1 + size2];
	   int i = 0;
	   int j = 0;
	   int k = 0;
	   for(k = 0; k < size1 + size2; k++) {
		   if(i < size1 && j < size2) {
			   if(arr.a[i] < brr.a[j]) {
				   res[k] = arr.a[i];
				   i++;
			   }else {
				   res[k] = brr.a[j];
				   j++;
			   }
		   }else {
			   break;
		   }
	   }
	   if(i < size1) {
		   res[k++] = arr.a[i++];
	   }
	   if(j < size2) {
		   res[k++] = brr.a[j++];
	   }
	   return res;
}

public static long[] getRandArray(int maxSize) {
    long upperBound = 1000;         // 随机数的上限为1000，可以任取其他数
    long[] result = new long[maxSize];  // 返回数组，内部装满随机产生的整数
    for(int j=0; j<maxSize; j++) // fill array with
    { // random numbers
        long n = (long)( java.lang.Math.random()*(upperBound-1) );
        result[j] = n;
    }   
    return result;
}

public static void addStudent(Greenhorn[] students, Greenhorn student, int len) {
	int i = 0;
	int j = len - 1;
	if(j > 0 && students[j - 1].id <= student.id) {
		  return;
	  }
	  while(i < j) {
		  int mid = (i + j) / 2;
		  if(students[mid].id >= student.id) {
			  j = mid;
		  }else {
			  i = mid + 1;
		  }
	  }
	  for(int k = len - 1; k > i; k--) {
		  students[k] = students[k - 1];
	  }
	  students[i] = student;
}
}  // end class OrdArray

